/*
 * @lc app=leetcode.cn id=52 lang=swift
 *
 * [52] N皇后 II
 */

// @lc code=start
class Solution {
    func totalNQueens(_ n: Int) -> Int {
        var res = 0

        func valid(_ chess: [[String]], _ row: Int, _ col: Int) -> Bool {
            for i in 0..<row {
                if chess[i][col] == "Q" {
                    return false
                }
            }

            var i = row - 1
            var j = col - 1
            while i >= 0 && j >= 0 {
                if chess[i][j] == "Q" {
                    return false
                }
                i -= 1
                j -= 1
            }

            i = row - 1
            j = col + 1
            while i >= 0 && j < chess.count {
                if chess[i][j] == "Q" {
                    return false
                }
                i -= 1
                j += 1
            }

            return true
        }

        func dns(_ chess: [[String]], _ row: Int) {
            if (chess.count == row) {
                res += 1
                return
            }
            for col in 0..<chess.count {
                if !valid(chess, row, col) {
                    continue
                }
                var newChess = chess
                newChess[row][col] = "Q"
                dns(newChess, row+1)
            }
        }

        dns(Array(repeating: Array(repeating: ".", count: n), count: n), 0)
        return res
    }
}
// @lc code=end

